package cn.hy.today;


import java.util.Arrays;

// https://leetcode.cn/problems/count-of-integers/?envType=daily-question&envId=2024-01-16
class Solution_2719 {

    private static final int MOD = 1_000_000_007;

    public int count(String num1, String num2, int min_sum, int max_sum) {
        int ans = calc(num2, min_sum, max_sum) - calc(num1, min_sum, max_sum) + MOD;
        int sum = 0;
        for (char c : num1.toCharArray()) {
            sum += c - '0';
        }
        if (max_sum >= sum && min_sum <= sum) {
            ans++; // num1 是合法的 补回来, num1 在上面被减去了
        }
        return ans % MOD;
    }

    private int calc(String s, int minSum, int maxSum) {
        int n = s.length();
        int[][] mem = new int[n][Math.min(9 * n, maxSum) + 1];
        for (int[] row : mem) {
            Arrays.fill(row, -1);
        }
        return dfs(0, 0, true, s.toCharArray(), minSum, maxSum, mem);
    }


    private int dfs(int i, int sum, boolean isLimit, char[] s, int minSum, int maxSum, int[][] mem) {

        if (sum > maxSum) {
            return 0;
        }
        if (i == s.length) {
            return sum >= minSum ? 1 : 0;
        }
        if (!isLimit && mem[i][sum] != -1) {
            return mem[i][sum];
        }
        int up = isLimit ? s[i] - '0' : 9;
        int res = 0;
        for (int d = 0; d <= up; d++) {
            res = (res + dfs(i + 1, sum + d, isLimit && (d == up), s, minSum, maxSum, mem)) % MOD;

        }
        if (!isLimit) {
            mem[i][sum] = res;
        }
        return res;

    }
}